package algorithm.leetcode.I1to100;

import algorithm.leetcode.TreeNode;

/**
 * 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
 * 尝试O(1)空间复杂度的解法
 */

public class Q99 {

    TreeNode prev, first, second;

    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = second.val;
        second.val = first.val;
        first.val = temp;
    }

    private void inorder(TreeNode node) {
        if (node == null) return;

        inorder(node.left);
        if (prev != null) {
            // 第一个逆序出现的地方,prev肯定是第一个待交换的节点
            if (prev.val > node.val && first == null) first = prev;
            // 等待与first交换的元素的要求是first中序遍历后面的 并且 最后一个小于或者等于first的元素
            // 可以想象成一个单调不降数组,只有两个元素被错误的交换,如何找到这两个元素
            // 这里不可以用else if,两个if必须都执行判断
            if (first != null && node.val <= first.val) second = node;
        }
        prev = node;
        inorder(node.right);
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        treeNode3.left = treeNode1;
        treeNode3.right = treeNode4;
        treeNode4.left = treeNode2;

        Q99 q99 = new Q99();
        q99.recoverTree(treeNode3);
    }

}
